package com.mamingchao.foundation.arraysort.insertsort;

import com.mamingchao.foundation.arraysort.Sortable;

/**
 * 不用 swap ，用临时变量 完成
 * 临时变量 存储 未排好序的子数组的 第一个值； 排好序的子队 比temp 大的，都向后移动一位，给temp 腾位置
 * Created by mamingchao on 2020/11/13.
 */
public class InsertSortWithTempImpl implements Sortable{

    @Override
    public void sort(int[] arr, int start, int end) {
        // check arg array

        if (arr == null || arr.length <2) {
            return;
        }

        int num = 0;

        for (int i = 1; i < arr.length  ; i++) {
            int temp = arr[i];
            int index = 0 ;

            for (int j = i ; j >0; j--) {
                //if the element is smaller than the previous element, then swap
                num ++;
                if(arr[j-1] > temp)  {
                    arr[j] = arr[j-1];
                } else {
                    index = j;
                    break;
                }
            }
            arr[index] = temp;
        }

        System.out.println("循环次数-" + num);
    }
}
